#![allow(dead_code, mutable_transmutes, non_camel_case_types, non_snake_case, non_upper_case_globals, unused_assignments, unused_mut)]
#![feature(extern_types)]
extern crate libc;
use primary::alloc_testing::*;
use primary::rb_tree::*;
use primary::compare_pointer::*;
use primary::compare_string::*;
use primary::compare_int::*;
use primary::hash_pointer::*;
use primary::hash_string::*;
use primary::hash_int::*;
extern "C" {
    pub type _RBTree;
    pub type _RBTreeNode;
    fn __assert_fail(
        __assertion: *const libc::c_char,
        __file: *const libc::c_char,
        __line: libc::c_uint,
        __function: *const libc::c_char,
    ) -> !;
                                                            }
pub const RB_TREE_NODE_RIGHT: RBTreeNodeSide = 1;
pub const RB_TREE_NODE_LEFT: RBTreeNodeSide = 0;
#[no_mangle]
pub static mut test_array: [libc::c_int; 1000] = [0; 1000];
#[no_mangle]
pub extern "C" fn find_subtree_height(mut node: *mut RBTreeNode) -> libc::c_int {
    if node.is_null() {
        return 0;
    }

    let mut left_subtree: *mut RBTreeNode = std::ptr::null_mut();
    let mut right_subtree: *mut RBTreeNode = std::ptr::null_mut();
    let mut left_height: libc::c_int = 0;
    let mut right_height: libc::c_int = 0;

    let node_box = unsafe { Box::from_raw(node) };
    unsafe {
        left_subtree = rb_tree_node_child(node, RB_TREE_NODE_LEFT);
        right_subtree = rb_tree_node_child(node, RB_TREE_NODE_RIGHT);
    }
    node = Box::into_raw(node_box);

    left_height = find_subtree_height(left_subtree);
    right_height = find_subtree_height(right_subtree);

    if left_height > right_height {
        left_height + 1
    } else {
        right_height + 1
    }
}
#[no_mangle]
pub extern "C" fn validate_tree(mut tree: *mut RBTree) {
    if tree.is_null() {
        return;
    }
    let tree_box = unsafe { Box::from_raw(tree) };
    
    tree = Box::into_raw(tree_box);
}
#[no_mangle]
pub extern "C" fn create_tree() -> *mut RBTree {
    let mut tree: *mut RBTree = std::ptr::null_mut();
    let mut i: libc::c_int = 0;

    tree = rb_tree_new(Some(int_compare));

    i = 0;
    while i < 1000 {
        unsafe {
            test_array[i as usize] = i;
        }
        rb_tree_insert(
            tree,
            unsafe { &mut *test_array.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeKey },
            unsafe { &mut *test_array.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeValue },
        );

        i += 1;
    }

    tree
}
#[no_mangle]
pub extern "C" fn test_rb_tree_new() {
    let mut tree: *mut RBTree = std::ptr::null_mut();

    tree = rb_tree_new(Some(int_compare));

    assert!(!tree.is_null(), "tree != NULL");

    let tree_box = unsafe { Box::from_raw(tree) };
    assert!(rb_tree_root_node(tree).is_null(), "rb_tree_root_node(tree) == NULL");
    assert_eq!(rb_tree_num_entries(tree), 0, "rb_tree_num_entries(tree) == 0");
    tree = Box::into_raw(tree_box);
    rb_tree_free(tree);
}
#[no_mangle]
pub extern "C" fn test_rb_tree_insert_lookup() {
    let mut tree: *mut RBTree = std::ptr::null_mut();
    let mut node: *mut RBTreeNode = std::ptr::null_mut();
    let mut i: libc::c_int = 0;
    let mut value: *mut libc::c_int = std::ptr::null_mut();

    tree = rb_tree_new(Some(int_compare));

    i = 0;
    while i < 1000 {
        unsafe {
            test_array[i as usize] = i;
            rb_tree_insert(
                tree,
                &mut *test_array.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeKey,
                &mut *test_array.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeValue,
            );
        }

        assert_eq!(rb_tree_num_entries(tree), i + 1, "rb_tree_num_entries(tree) == i + 1");
        validate_tree(tree);
        i += 1;
    }

    assert!(!rb_tree_root_node(tree).is_null(), "rb_tree_root_node(tree) != NULL");

    i = 0;
    while i < 1000 {
        node = rb_tree_lookup_node(tree, &mut i as *mut libc::c_int as RBTreeKey);
        value = rb_tree_node_key(node) as *mut libc::c_int;

        assert!(!node.is_null(), "node != NULL");
        assert_eq!(unsafe { *value }, i, "*value == i");

        value = rb_tree_node_value(node) as *mut libc::c_int;
        assert_eq!(unsafe { *value }, i, "*value == i");
        i += 1;
    }

    i = -1;
    assert!(rb_tree_lookup_node(tree, &mut i as *mut libc::c_int as RBTreeKey).is_null(), "rb_tree_lookup_node(tree, &i) == NULL");

    i = 1000 + 100;
    assert!(rb_tree_lookup_node(tree, &mut i as *mut libc::c_int as RBTreeKey).is_null(), "rb_tree_lookup_node(tree, &i) == NULL");

    rb_tree_free(tree);
}
#[no_mangle]
pub extern "C" fn test_rb_tree_child() {
    let mut tree: *mut RBTree = std::ptr::null_mut();
    let mut root: *mut RBTreeNode = std::ptr::null_mut();
    let mut left: *mut RBTreeNode = std::ptr::null_mut();
    let mut right: *mut RBTreeNode = std::ptr::null_mut();
    let mut values: [libc::c_int; 3] = [1, 2, 3];
    let mut p: *mut libc::c_int = std::ptr::null_mut();
    let mut i: libc::c_int = 0;

    tree = rb_tree_new(Some(int_compare));

    while i < 3 {
        unsafe {
            rb_tree_insert(
                tree,
                &mut *values.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeKey,
                &mut *values.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeValue,
            );
        }
        i += 1;
    }

    root = rb_tree_root_node(tree);
    let root_box = unsafe { Box::from_raw(root) };
    p = rb_tree_node_value(root) as *mut libc::c_int;
    unsafe {
        assert!(*p == 2, "Expected *p to be 2");
    }

    left = rb_tree_node_child(root, RB_TREE_NODE_LEFT);
    let left_box = unsafe { Box::from_raw(left) };
    p = rb_tree_node_value(left) as *mut libc::c_int;
    unsafe {
        assert!(*p == 1, "Expected *p to be 1");
    }

    right = rb_tree_node_child(root, RB_TREE_NODE_RIGHT);
    let right_box = unsafe { Box::from_raw(right) };
    p = rb_tree_node_value(right) as *mut libc::c_int;
    unsafe {
        assert!(*p == 3, "Expected *p to be 3");
    }

    assert!(rb_tree_node_child(root, 10000).is_null(), "Expected rb_tree_node_child(root, 10000) to be NULL");
    assert!(rb_tree_node_child(root, 2).is_null(), "Expected rb_tree_node_child(root, 2) to be NULL");

    root = Box::into_raw(root_box);
    left = Box::into_raw(left_box);
    right = Box::into_raw(right_box);

    rb_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_out_of_memory() {}
#[no_mangle]
pub extern "C" fn test_rb_tree_free() {
    let mut tree: *mut RBTree = std::ptr::null_mut();

    tree = rb_tree_new(Some(int_compare));
    let tree_box = unsafe { Box::from_raw(tree) };
    rb_tree_free(tree);
    tree = Box::into_raw(tree_box);

    tree = create_tree();
    let tree_box = unsafe { Box::from_raw(tree) };
    rb_tree_free(tree);
    tree = Box::into_raw(tree_box);
}
#[no_mangle]
pub extern "C" fn test_rb_tree_lookup() {
    let mut tree: *mut RBTree = std::ptr::null_mut();
    let mut i: libc::c_int = 0;
    let mut value: *mut libc::c_int = std::ptr::null_mut();

    tree = create_tree();
    let tree_box = unsafe { Box::from_raw(tree) };

    i = 0;
    while i < 1000 {
        value = rb_tree_lookup(tree, &mut i as *mut libc::c_int as RBTreeKey) as *mut libc::c_int;
        assert!(!value.is_null(), "value != NULL");
        assert_eq!(unsafe { *value }, i, "*value == i");
        i += 1;
    }

    i = -1;
    assert!(rb_tree_lookup(tree, &mut i as *mut libc::c_int as RBTreeKey).is_null(), "rb_tree_lookup(tree, &i) == NULL");

    i = 1001;
    assert!(rb_tree_lookup(tree, &mut i as *mut libc::c_int as RBTreeKey).is_null(), "rb_tree_lookup(tree, &i) == NULL");

    i = 8724897;
    assert!(rb_tree_lookup(tree, &mut i as *mut libc::c_int as RBTreeKey).is_null(), "rb_tree_lookup(tree, &i) == NULL");

    tree = Box::into_raw(tree_box);
    rb_tree_free(tree);
}
#[no_mangle]
pub extern "C" fn test_rb_tree_remove() {
    let mut tree: *mut RBTree = std::ptr::null_mut();
    let mut i: libc::c_int = 0;
    let mut x: libc::c_int = 0;
    let mut y: libc::c_int = 0;
    let mut z: libc::c_int = 0;
    let mut value: libc::c_int = 0;
    let mut expected_entries: libc::c_int = 0;

    unsafe {
        tree = create_tree();
    }

    i = 1000 + 100;
    assert_eq!(rb_tree_remove(tree, unsafe { &mut i as *mut libc::c_int as RBTreeKey }), 0);

    i = -1;
    assert_eq!(rb_tree_remove(tree, unsafe { &mut i as *mut libc::c_int as RBTreeKey }), 0);

    expected_entries = 1000;
    x = 0;
    while x < 10 {
        y = 0;
        while y < 10 {
            z = 0;
            while z < 10 {
                value = z * 100 + (9 - y) * 10 + x;
                assert_ne!(rb_tree_remove(tree, unsafe { &mut value as *mut libc::c_int as RBTreeKey }), 0);
                validate_tree(tree);
                expected_entries -= 1;
                assert_eq!(rb_tree_num_entries(tree), expected_entries);
                z += 1;
            }
            y += 1;
        }
        x += 1;
    }

    unsafe {
        assert!((rb_tree_root_node(tree)).is_null());
        rb_tree_free(tree);
    }
}
#[no_mangle]
pub extern "C" fn test_rb_tree_to_array() {
    let mut tree: *mut RBTree = std::ptr::null_mut();
    let mut entries: [libc::c_int; 10] = [
        89, 23, 42, 4, 16, 15, 8, 99, 50, 30,
    ];
    let mut sorted: [libc::c_int; 10] = [
        4, 8, 15, 16, 23, 30, 42, 50, 89, 99,
    ];
    let num_entries: libc::c_int = (std::mem::size_of::<[libc::c_int; 10]>()
        / std::mem::size_of::<libc::c_int>()) as libc::c_int;
    let mut i: libc::c_int = 0;
    let mut array: *mut *mut libc::c_int = std::ptr::null_mut();

    tree = rb_tree_new(
        (Some(int_compare)),
    );

    i = 0;
    while i < num_entries {
        unsafe {
            rb_tree_insert(
                tree,
                &mut *entries.as_mut_ptr().offset(i as isize) as *mut libc::c_int as RBTreeKey,
                std::ptr::null_mut(),
            );
        }
        i += 1;
    }

    assert_eq!(rb_tree_num_entries(tree), num_entries);
    array = rb_tree_to_array(tree) as *mut *mut libc::c_int;

    i = 0;
    while i < num_entries {
        unsafe {
            assert_eq!(**array.offset(i as isize), sorted[i as usize]);
        }
        i += 1;
    }

    unsafe {
        alloc_test_free(array as *mut libc::c_void);
        rb_tree_free(tree);
    }
}








































